1922D - Berserk Monsters - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    // freopen("d.out", "w", stdout);
    // freopen("d.err", "w", stderr);
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 2), d(n + 2);
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> d[i];
        vector<int> L(n + 2), R(n + 2);
        for (int i = 1; i <= n; i++)
            L[i] = i - 1, R[i] = i + 1;
        R[0] = 1, L[n + 1] = n;
        L[0] = -1, R[n + 1] = -1;
        set<int> die, rebuild;
        auto process = [&](int x) {
            if (L[x] == -1 || R[x] == -1) return;
            int recieve = a[L[x]] + a[R[x]];
            if (recieve > d[x]) die.insert(x);
        };
        auto remove = [&](int x) {
            L[R[x]] = L[x];
            R[L[x]] = R[x];
            rebuild.insert(L[x]);
            rebuild.insert(R[x]);
            L[x] = R[x] = -1;
        };
        for (int i = 1; i <= n; i++)
            process(i);
        for (int i = 1; i <= n; i++) {
            cout << die.size() << " ";
            for (int x : die)
                remove(x);
            // ! debug start
            // cerr << "L : ";
            // for (int j = 1; j <= n; j++)
            //     cerr << L[j] << " ";
            // cerr << endl;
            // cerr << "R : ";
            // for (int j = 1; j <= n; j++)
            //     cerr << R[j] << " ";
            // cerr << endl;
            // cerr << "rebuild : ";
            // for (int j : rebuild)
            //     cerr << j << " ";
            // cerr << endl;
            // ! debug done
            die.clear();
            for (int x : rebuild)
                process(x);
            rebuild.clear();
        }
        cout << endl;
    }
    return 0;
}